package com.jd.sunny.java.collection;

import java.util.BitSet;

/**
 * @Description:BitSet
 * @author:sunlin
 * @since:2012-12-07 13:59
 * @version:1.0.0
 */
public class TestBitSet {

    /**
     * this program runs the Sieve of Eratjpstenes benchmark.It computes all primes up to 2000000.
     * @param args
     */
    public static void main(String[] args){
        int n = 2000000;
        long start = System.currentTimeMillis();

        BitSet bitSet = new BitSet( n + 1);
        int count = 0;
        int i;
        // set
        for ( i = 2;i <= n;i++){
            bitSet.set(i);
        }
        i = 2;

        //time = 134
        while (i*i<=n){
            if(bitSet.get(i)){
                count++;
                int k = i + i;
                while (k < n){
                    bitSet.clear(k);
                    k = k + i;
                }
            }
            i++;
        }
        while (i<=n){
            if(bitSet.get(i)){
                count++;
            }
            i++;
        }
        //my arithmetic is simple but speed is little slower. tiem= 151
//        for(int i = 2;i < n + 1;i++){
//            if(bitSet.get(i)){
//                count++;
//                int k = i + i;
//                while(k < n){
//                    bitSet.clear(k);
//                    k = k +  i;
//                }
//            }
//        }
        long end = System.currentTimeMillis();
        System.out.println("primes count=" + count);
        System.out.println(end -start);
    }

}
